//
//  Problem24.swift
//  LeetCode - 24 两两交换链表中的节点
//
//  Created by 武侠 on 2020/7/14.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 [24 两两交换链表中的节点]
 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 
 示例:
 给定 1->2->3->4, 你应该返回 2->1->4->3.
 
 */
class Problem24: NSObject {
    func solution() {
        let nums = [1, 2, 3, 4]
        if let node = createList(nums) {
            let node = swapPairs1(node)
            printNode(node)
        }
        
    }
    
    // 方法一: 挨个遍历 第一个和第二个进行交换
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil{
            return head
        }
        
        let list = head?.next
        var first = head
        var second = head?.next
        var last:ListNode? = nil
        while first != nil, second != nil {
            let tempNode = second?.next
            second?.next = first
            first?.next = tempNode
            last?.next = second
            
            last = first
            first = tempNode
            second = first?.next
        }
        
        return list
    }
    
    // 方法二: 递归, 先交换前2个, 后面的递归
    func swapPairs1(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil{
            return head
        }
        
        let next = head?.next
        head?.next = swapPairs1(next?.next)
        next?.next = head
        
        return next
    }
    
    // 打印Node
    func printNode(_ list: ListNode?) {
        var head: ListNode? = list
        var nums:[Int] = []
        while head != nil {
            nums.append(head!.val)
            head = head?.next
        }
        print(nums)
    }
    
    
}
